package com.example.hot100;

import java.util.Arrays;

/**
 * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 *  示例 1：
 * 输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
 *
 *  示例 2：
 * 输入：nums = [1,2,3,5]
 * 输出：false
 * 解释：数组不能分割成两个元素和相等的子集。
 */
public class Leetcode416_CanPartition {
    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println(new Solution().canPartition(nums));
    }

    static class Solution {
        /**
         * 动态规划
         *换一种表述：给定一个只包含正整数的非空数组 nums，判断是否可以从数组中选出一些数字，使得这些数字的和等于整个数组的元素和的一半。
         * 因此这个问题可以转换成「0-10−1 背包问题」。
         * 与传统的「0-10−1 背包问题」的区别在于，传统的「0-10−1 背包问题」要求选取的物品的重量之和不能超过背包的总容量，
         * 本题则要求选取的数字的和恰好等于整个数组的元素和的一半
         *
         * dp[i][j] 表示 在nums数组的 0~i(包含0,也包含i) 选取若干个数(可以是0个)之和能否等于j
         *
         * @param nums
         * @return
         */
        private boolean canPartition1(int[] nums) {
            int len = nums.length;
            if (len < 2) return false;
            int maxVal = Arrays.stream(nums).max().getAsInt();
            int sum = Arrays.stream(nums).sum();
            int target;
            if ((maxVal > (target = sum >> 1)) || sum % 2 != 0) return false;
            boolean[][] dp = new boolean[len][target + 1]; // dp[i][j] 表示 在nums数组的 0~i 选取若干个数(可以是0个)之和能否等于j

            // 边界情况的处理
            for (int i = 0; i < len; i++) { // 边界情况一: 不选取任何正整数，则被选取的正整数等于 0
                dp[i][0] = true;
            }
            dp[0][nums[0]] = true; // 边界情况二: 选取区间为[0, 0]时，只有合为nums[0]的才为true

            // 状态计算
            for (int i = 1; i < len; i++) {
                int curNum = nums[i];
                for (int j = 1; j <= target; j++) {
                    if (j >= curNum)  // j >= nums[i]，则对于当前的数字 nums[i]，可以选取也可以不选取，两种情况只要有一个为true 就是true
                        dp[i][j] = dp[i - 1][j] // 不选当前数字
                                | dp[i - 1][j - curNum];// 选择当前数字
                    else // 在选取的数字的和等于 j 的情况下无法选取当前的数字 nums[i], 因为 j < nums[i]
                        dp[i][j] = dp[i - 1][j];
                }
            }

            return dp[len - 1][target];
        }

        public boolean canPartition(int[] nums) {
            return canPartition1(nums);
        }
    }
}
